package com.pan.common.algorithm.basic.sortbasic;

import org.apache.commons.lang3.ArrayUtils;

/**
 * 选择排序
 * 工作原理是：
 * 第一次从待排序的数据元素中选出最小的元素，
 * 将起始位置的元素与最小元素进行位置互换，然后再从剩余的未排序元素中寻找到最小元素，
 * 与第二位的元素进行互换。以此类推，直到全部待排序的数据元素的个数为零。
 * 选择排序是不稳定的排序方法。
 *
 */
public class SelectionSort{

    // 我们的算法类不允许产生任何实例
    private SelectionSort(){}

    public static void sort(Comparable[] arr){

        int n = arr.length;
        for( int i = 0 ; i < n ; i ++ ){
            // 寻找[i, n)区间里的最小值的索引
            int minIndex = i;
            for( int j = i + 1 ; j < n ; j ++ )
                // 使用compareTo方法比较两个Comparable对象的大小
                if( arr[j].compareTo( arr[minIndex] ) < 0 )
                    minIndex = j;

            swap( arr , i , minIndex);
        }


    }

    /**
     * 将i与j位置的元素进行互换
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void mySelectionSort(Integer[] arr){

        int length = arr.length;

        for(int j=0;j<length;j++){
            int index = j;
            for(int i=j+1;i<length;i++){
                if(arr[i]<arr[index]){
                    index=i;
                }
            }
            swapInt(arr,j,index);
        }
    }

    /**
     * 学会写辅助函数
     * @param arr
     * @param i
     * @param j
     */
    private static void swapInt(Integer[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 测试 SelectionSort
    public static void main(String[] args) {

        int N = 20;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100);
        //SortTestHelper.testSort("bobo.algo.SelectionSort", arr);
        System.out.println(ArrayUtils.toString(arr));
        Integer[] arr2 = arr;
        System.out.println(arr2==arr);
        mySelectionSort(arr);
        System.out.println(ArrayUtils.toString(arr));

        sort(arr2);
        System.out.println(ArrayUtils.toString(arr2));

        return;
    }
}